{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tuple with Same Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tupleSameProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #同积元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>不同</strong> 正整数组成的数组 <code>nums</code> ，请你返回满足&nbsp;<code>a * b = c * d</code> 的元组<em> </em><code>(a, b, c, d)</code><em> </em>的数量。其中 <code>a</code>、<code>b</code>、<code>c</code> 和 <code>d</code> 都是 <code>nums</code> 中的元素，且 <code>a != b != c != d</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,4,6]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>存在 8 个满足题意的元组：\n",
    "(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)\n",
    "(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4,5,10]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>存在 16 个满足题意的元组：\n",
    "(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)\n",
    "(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)\n",
    "(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)\n",
    "(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tuple-with-same-product](https://leetcode.cn/problems/tuple-with-same-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tuple-with-same-product](https://leetcode.cn/problems/tuple-with-same-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,4,6]', '[1,2,4,5,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        li = []\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                li.append(nums[i]*nums[j])\n",
    "        ans=0\n",
    "        nn = len(li)\n",
    "        c = 1\n",
    "        li.sort()\n",
    "        for i in range(1,nn):\n",
    "            if li[i]!=li[i-1]:\n",
    "                ans +=c*(c-1)*4\n",
    "                c =1\n",
    "            else:\n",
    "                c+=1\n",
    "\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, ns: List[int]) -> int:\n",
    "        L=len(ns)\n",
    "        # dp = [[0 for _ in range(L)] for _ in range(L)]\n",
    "        res =[]\n",
    "        for i in range(L-1):\n",
    "            for j in range(i+1,L):\n",
    "                res.append(ns[i] * ns[j])\n",
    "        res = sorted(res)\n",
    "        # print(res)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(res):\n",
    "            cnt = 1\n",
    "            while i < len(res) and res[i] == res[i-1] or 0:\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            ans += cnt * (cnt - 1) // 2\n",
    "            i +=1\n",
    "        return ans * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums):\n",
    "        length = len(nums)\n",
    "        count = 0\n",
    "        if length < 4:\n",
    "            return 0\n",
    "        product_list = list()\n",
    "        for i in range(length):\n",
    "            a = nums[i]\n",
    "            for j in range(i+1,length):\n",
    "                b = nums[j]\n",
    "                rst = a * b\n",
    "                product_list.append(rst)\n",
    "        length = len(product_list)\n",
    "        sort_list = sorted(product_list)\n",
    "        equal_count = 0\n",
    "        i = 0\n",
    "        while (i < length - 1):\n",
    "            if sort_list[i] == sort_list[i+1]:\n",
    "                equal_count += 1\n",
    "            else:\n",
    "                if equal_count > 0:\n",
    "                    count += sum(range(1,equal_count + 1)) * 8\n",
    "                equal_count = 0 \n",
    "            i += 1\n",
    "        if equal_count > 0:\n",
    "            count += sum(range(1,equal_count + 1)) * 8    \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        temp = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                m = nums[i]*nums[j]\n",
    "                if m in temp.keys():\n",
    "                    temp[m] += 1\n",
    "                else:\n",
    "                    temp[m] = 1\n",
    "        cnt = 0\n",
    "        for v in temp.values():\n",
    "            cnt += v*(v-1)/2*8\n",
    "        return int(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cnt =0 \n",
    "        dic = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                t = nums[i]*nums[j]\n",
    "                cnt += dic[t]*8 \n",
    "                dic[t] +=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        map = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                key = nums[i] * nums[j]\n",
    "                if key in map:\n",
    "                    res += 8 * map[key]\n",
    "                map[key] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/19 00:19\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                x = nums[i] * nums[j]\n",
    "                cnt[x] += 1\n",
    "        return sum(v * (v - 1) // 2 for v in cnt.values()) << 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        sum_list = []\n",
    "\n",
    "        len_tmp = len(nums)\n",
    "        for i in range(len_tmp - 1):\n",
    "            for j in range(i + 1, len_tmp):\n",
    "#                sum_list.append([i, j, nums[i] * nums[j]])\n",
    "                 sum_list.append(nums[i] * nums[j])\n",
    "#                print(sum_list)\n",
    "        sum1 = 0\n",
    "\n",
    "        sum_list.sort()\n",
    "        print(sum_list)\n",
    "\n",
    "        len_sum = len(sum_list)\n",
    "\n",
    "        seq = 0\n",
    "        flag = 0\n",
    "        while seq < len_sum - 1:\n",
    "            if sum_list[seq] == sum_list[seq + 1]:\n",
    "                sum1 += 1\n",
    "                seq += 1\n",
    "                flag += 1\n",
    "            elif flag > 1:\n",
    "                sum1 += int((flag + 1) * flag / 2) - flag\n",
    "                seq += 1\n",
    "                flag = 0\n",
    "            else:\n",
    "                seq += 1\n",
    "                flag = 0\n",
    "       \n",
    "        return sum1 * 8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        chengji=[]\n",
    "        for i in range(0,l):\n",
    "            for j in range(i,l):\n",
    "                if i!=j:\n",
    "                    chengji.append(nums[i]*nums[j])\n",
    "        chengji.sort()\n",
    "        print(chengji)\n",
    "        num=1\n",
    "        ans=0\n",
    "        now=chengji[0]\n",
    "        for k in range(1,len(chengji)):\n",
    "            if now==chengji[k]:\n",
    "                num+=1\n",
    "            else:\n",
    "                now=chengji[k]\n",
    "                ans+=num*(num-1)*4\n",
    "                num=1\n",
    "                \n",
    "        return ans+num*(num-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        Product=[]\n",
    "        for j in range(len(nums)):\n",
    "            for k in range(j+1,len(nums)):\n",
    "                  Product.append(nums[j]*nums[k])\n",
    "        Product.sort()\n",
    "        j,sum=1,0\n",
    "        print(Product)\n",
    "        for i in range(1,len(Product)):\n",
    "              if(Product[i]==Product[i-1]):\n",
    "                j+=1 \n",
    "              else:\n",
    "                   sum+=(j* (j - 1) / 2)\n",
    "                   j=1\n",
    "        return int(sum*8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        from math import factorial as f\n",
    "        dic = {}\n",
    "        s = set()\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                res = nums[i] * nums[j]\n",
    "                if res not in dic:\n",
    "                    dic[res] = 1\n",
    "                else:\n",
    "                    dic[res] += 1\n",
    "                    if res not in s:\n",
    "                        s.add(res)\n",
    "        combs = [f(dic[res]) // (2 * f(dic[res] - 2)) for res in s]\n",
    "        return 8 * sum(combs)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        couples=0\n",
    "        count={}\n",
    "        multi_set=set()\n",
    "        for i,num_1 in enumerate(nums[:-1]):\n",
    "            for j,num_2 in enumerate(nums[i+1:]):\n",
    "                multi_value = num_1 * num_2\n",
    "                if multi_value in multi_set:\n",
    "                    count[multi_value]+=1\n",
    "                else:\n",
    "                    multi_set.add(multi_value)\n",
    "                    count[multi_value]=1\n",
    "        for item in multi_set:\n",
    "            if count[item]>=2:\n",
    "                couples+=(count[item]*(count[item]-1))\n",
    "        return int(couples*4)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        vis={}\n",
    "        product = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                a=nums[i] * nums[j]\n",
    "                product.append(a)\n",
    "                if(a not in vis):vis[a]=1\n",
    "                else:vis[a]+=1\n",
    "        visit=list(vis.values())\n",
    "        for i in range(len(visit)):\n",
    "            n=visit[i]\n",
    "            count+=(n*(n-1)//2)*8\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        cj = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                tmp = str(nums[i]*nums[j])\n",
    "                if tmp in cj:\n",
    "                    cj[tmp] += 1\n",
    "                else:\n",
    "                    cj[tmp] = 1\n",
    "        ans = 0\n",
    "        for k in cj:\n",
    "            ans += cj[k] * (cj[k] - 1) * 4\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # products = [x * nums[j] for i,x in enumerate(nums) for j in range(i+1,n)]\n",
    "        # c = Counter(products)\n",
    "        c = Counter([x * nums[j] for i,x in enumerate(nums) for j in range(i+1,n)])\n",
    "        ans = 0\n",
    "        for x in c.values():\n",
    "            if x > 1:\n",
    "                ans += x * (x-1) * 4\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=Counter([nums[i]*nums[j] for i in range(n) for j in range(i+1,n)])\n",
    "        ans=0\n",
    "        for _,v in cnt.items():\n",
    "            ans += v*(v-1)*4\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter([nums[i] * nums[j] for i in range(n) for j in range(i + 1, n)])\n",
    "        ans = 0\n",
    "        for _, v in cnt.items():\n",
    "            ans += v * (v - 1) * 4\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        db = set()\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for i in range (len(nums) - 1):\n",
    "            for j in range (i + 1,len(nums)):\n",
    "                if nums[i] * nums[j] not in cnt:\n",
    "                   cnt[nums[i] * nums[j]] = 0\n",
    "                if nums[i] * nums[j] in db:\n",
    "                   ans += 8 * cnt[nums[i] * nums[j]]\n",
    "                else:\n",
    "                    db.add(nums[i] * nums[j])\n",
    "                cnt[nums[i] * nums[j]] += 1\n",
    "        return ans\n",
    "\n",
    "                   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        # if length < 4: return 0 \n",
    "        count = 0\n",
    "        arr = []\n",
    "        for i in range(length):\n",
    "            for j in range(i):\n",
    "                arr.append(nums[i] * nums[j])\n",
    "        array = self.quicksort(arr)\n",
    "        \n",
    "        i = 0\n",
    "        while(i < len(array)-1):\n",
    "            count_tmp = 0\n",
    "            tmp = array[i]\n",
    "            while(array[i+1]==tmp):\n",
    "                i = i+1\n",
    "                count_tmp = count_tmp + 1\n",
    "            i = i + 1\n",
    "            count = count + count_tmp*(count_tmp+1)/2\n",
    " \n",
    "        return int(count*8)\n",
    "    \n",
    "    def quicksort(self, arr):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        pivot = arr[len(arr) // 2]  \n",
    "        left = [x for x in arr if x < pivot]  \n",
    "        middle = [x for x in arr if x == pivot]  \n",
    "        right = [x for x in arr if x > pivot]  \n",
    "\n",
    "        array = self.quicksort(left) + middle + self.quicksort(right)\n",
    "        return array\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                dp[i][j] = nums[i] * nums[j]\n",
    "        res = Counter()\n",
    "        for i in dp:\n",
    "            res.update(i)\n",
    "        res.pop(0)\n",
    "        ans = 0\n",
    "        for i in res:\n",
    "            if (r := res[i]) > 1:\n",
    "                ans += r * (r - 1)\n",
    "        return ans * 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                dp[i][j] = nums[i] * nums[j]\n",
    "        res = Counter()\n",
    "        for i in dp:\n",
    "            res.update(i)\n",
    "        res.pop(0)\n",
    "        ans = 0\n",
    "        for i in res:\n",
    "            if (r := res[i]) > 1:\n",
    "                ans += r * (r - 1)\n",
    "        return ans * 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "            # def jiecheng(n):\n",
    "            #     x = 1\n",
    "            #     for i in range(1, n+1):\n",
    "            #         x *= i\n",
    "            #     return x\n",
    "            mul = [[-1 for i in range(len(nums))] for j in range(len(nums))]\n",
    "            dic={}\n",
    "            ans=0\n",
    "            for i in range(len(nums)):\n",
    "                for j in range(len(nums)):\n",
    "                    if i>j:\n",
    "                        mul[i][j]=nums[i]*nums[j]\n",
    "            for i in range(len(mul)):\n",
    "                for j in range(len(mul[i])):\n",
    "                    if mul[i][j]!=-1:\n",
    "                        dic[mul[i][j]]=0\n",
    "            for i in range(len(mul)):\n",
    "                for j in range(len(mul[i])):\n",
    "                    if mul[i][j]!=-1:\n",
    "                        dic[mul[i][j]]+=1\n",
    "            for key in dic:\n",
    "                if dic[key]>1:\n",
    "                    ans+=8*dic[key]*(dic[key]-1)/2\n",
    "\n",
    "            return int(ans)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        arr = Counter()\n",
    "        for a, b in combinations(nums,2):\n",
    "            arr[a*b] += 1\n",
    "        res = list(comb(v, 2) for v in arr.values())\n",
    "        return sum(res * 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                cnt[nums[i]*nums[j]] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for cm in cnt.most_common():\n",
    "            ans += cm[1]*(cm[1]-1)//2\n",
    "        return ans * 8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1726 lang=python\n",
    "#\n",
    "# [1726] 同积元组\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def tupleSameProduct(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        stack = [[]for i in range(len(nums))]\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                a = nums[i]\n",
    "                b = nums[j]\n",
    "                if b == 0:\n",
    "                    continue\n",
    "                if a/b not in stack[j]:\n",
    "                    ans += 4 * dic.get(a/b,0)\n",
    "                    dic[a/b] = dic.get(a/b,0) + 1\n",
    "                    stack[i].append(a/b)\n",
    "                else:\n",
    "                    ans += 4 * (dic.get(a/b,0) - 1)\n",
    "                    dic[a/b] = dic.get(a/b,0) + 1\n",
    "                    stack[i].append(a/b)\n",
    "\n",
    "        return ans \n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        d = []\n",
    "        for i in combinations(nums,2):\n",
    "            d.append(i[0]*i[1])\n",
    "        a = dict(Counter(d))\n",
    "        ak = a.values()\n",
    "        r = 0\n",
    "        for i in ak:\n",
    "            r += i * (i-1) / 2\n",
    "        return int(r*8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        from itertools import combinations\n",
    "\n",
    "        lst = [i*j for i,j in combinations(nums,2)]\n",
    "        lst = dict(Counter(lst))\n",
    "        ans = 0\n",
    "\n",
    "        for v in lst.values() :\n",
    "            if v > 1:\n",
    "                ans += v*(v-1)/2\n",
    "        return int(8*ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        dict_num = {}\n",
    "        ret = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(len(nums) - i - 1):\n",
    "                result = nums[i] * nums[j+i+1]\n",
    "                if (dict_num.get(result)==None):\n",
    "                    dict_num[result] = 1\n",
    "                else:\n",
    "                    dict_num[result] += 1\n",
    "        print(dict_num.items())\n",
    "        for k in dict_num.values():\n",
    "            print(k)\n",
    "            \n",
    "            ret += k * (k - 1) * 4\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        # a=[[0]*(i) for i in range(1,n)]\n",
    "        b,d={},0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1):\n",
    "                c=nums[i+1]*nums[j]\n",
    "                if c in b:\n",
    "                    # if b[c][0]!=i and b[c][1]!=j:\n",
    "                    d+=b[c][2]*8\n",
    "                    b[c]=(i,j,b[c][2]+1)\n",
    "                else:b[c]=(i,j,1)\n",
    "                # a[i][j]=c\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        tmp = [x * y for x, y in list(combinations(nums, 2))]\n",
    "        return sum(x * (x - 1) // 2 * 8 for x in Counter(tmp).values() if x > 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: list[int]) -> int:\n",
    "        b=len(nums)\n",
    "        f=[0]*(3000005)\n",
    "        s=[0]*(3005006)\n",
    "        c=0\n",
    "        k=1000005\n",
    "        def se(n):\n",
    "            p=n\n",
    "            p%=k\n",
    "            while(f[p]!=0 and f[p]!=n):\n",
    "                p+=1\n",
    "                #print(4)\n",
    "                if p==k:\n",
    "                    p=0\n",
    "            f[p] = n\n",
    "            return p\n",
    "        for i in range(b):\n",
    "            for j in range(i+1,b):\n",
    "                s[se(nums[i]*nums[j])]+=1\n",
    "        d=len(s)\n",
    "        #print(s)\n",
    "        for i in range(d):\n",
    "            if s[i]>1:\n",
    "                #print(s[i])\n",
    "                #print()\n",
    "                c+=s[i]*(s[i]-1)//2\n",
    "        return c*8\n",
    "#print(tupleSameProduct([1,2,4,5,10]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        mydic={}\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]*nums[j] not in mydic:\n",
    "                    mydic[nums[i]*nums[j]]=[min(nums[i], nums[j]),]\n",
    "                else:\n",
    "                    mydic[nums[i]*nums[j]].append( min(nums[i], nums[j]) )\n",
    "        ans=0\n",
    "        #print(mydic)\n",
    "        for k,v in mydic.items():\n",
    "            if len(v)>=2:\n",
    "                ans+= 8*len(v)*(len(v)-1)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        # o(n2)\n",
    "        dicts = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                product = nums[i]*nums[j]\n",
    "                if product not in dicts.keys():\n",
    "                    dicts[product] = [nums[i],nums[j]]\n",
    "                else:\n",
    "                    dicts[product].append(nums[i])\n",
    "                    dicts[product].append(nums[j])\n",
    "        # 2 = 0\n",
    "        # 4 = 8\n",
    "        # 6 = 3*2/2*8\n",
    "        # \n",
    "        rt = 0\n",
    "        for key in dicts.keys():\n",
    "            length = int(len(dicts[key])/2)\n",
    "            rt+= int(length*(length-1)/2*8)\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        t = [nums[i]*nums[j] for i in range(len(nums)) for j in range(i+1,len(nums))]\n",
    "        ans = 0\n",
    "        for x in Counter(t).most_common():\n",
    "            if x[1] == 1:\n",
    "                break\n",
    "            else:\n",
    "                ans += x[1] * (x[1] - 1)//2\n",
    "        return ans * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        cnt = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                try:\n",
    "                    cnt[nums[i] * nums[j]] += 1\n",
    "                except:\n",
    "                    cnt[nums[i] * nums[j]] = 1\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            if v < 2:\n",
    "                continue\n",
    "            ans += int(comb(v, 2)) * 8\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import math\n",
    "from collections import defaultdict\n",
    "from scipy.special import comb, perm\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        multiples = defaultdict()\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            j = i + 1\n",
    "            while j < n:\n",
    "                if nums[i] * nums[j] not in multiples.keys():\n",
    "                    multiples.update({nums[i] * nums[j]: 1})\n",
    "                else:\n",
    "                    multiples[nums[i] * nums[j]] += 1\n",
    "                j += 1\n",
    "        # print(multiples)\n",
    "        res = 0\n",
    "        for k, v in multiples.items():\n",
    "            if v >= 2:\n",
    "                res += comb(v, 2)\n",
    "        return int(res * 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        dict={}\n",
    "        list=[]\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if i!=j:\n",
    "                    list.append(nums[i]*nums[j])\n",
    "        for i in list:\n",
    "            if i in dict:\n",
    "                dict[i]+=1\n",
    "            else:\n",
    "                dict[i]=1\n",
    "        for key in dict.keys():\n",
    "            if dict[key]>2 and dict[key]%2==0:    \n",
    "                v=dict[key]\n",
    "                n=int(v/2)\n",
    "                ans+=n*(n-1)*4\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        h = Counter()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                h[nums[i] * nums[j]] += 1\n",
    "        res = 0\n",
    "        print(h)\n",
    "        for [k, v] in h.items():\n",
    "            res += (v - 1) * v * 4\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        #c=[]\n",
    "        #while i<len(nums):\n",
    "         #   j=i+1\n",
    "          #  while j<len(nums):\n",
    "           #     c.append(nums[i]*nums[j])\n",
    "            #    j=j+1\n",
    "            #i=i+1\n",
    "        c=Counter(nums[i]*nums[j] for i in range(len(nums)) for j in range(i+1,len(nums)))\n",
    "        print(c)\n",
    "        dic=collections.defaultdict(int)\n",
    "        k=0\n",
    "        for item in c:\n",
    "            #c[item]=c[item]+1\n",
    "            if c[item]>=2:\n",
    "                k=k+c[item]*(c[item]-1)/2\n",
    "        #print(dic)\n",
    "        return 8*int(k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        a=[[0]*(i) for i in range(1,n)]\n",
    "        b,d={},0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1):\n",
    "                c=nums[i+1]*nums[j]\n",
    "                if c in b:\n",
    "                    if b[c][0]!=i and b[c][1]!=j:\n",
    "                        d+=b[c][2]*8\n",
    "                        b[c]=(i,j,b[c][2]+1)\n",
    "                else:b[c]=(i,j,1)\n",
    "                a[i][j]=c\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        c=list(itertools.combinations(nums, 2))\n",
    "        d=dict()\n",
    "        for a,b in c:\n",
    "            p=a*b\n",
    "            if d.get(p):\n",
    "                d[p]+=1\n",
    "            else:\n",
    "                d[p]=1\n",
    "        for q in d.values():\n",
    "            if q>1:\n",
    "                res += 8 * (math.factorial(q)//(math.factorial(2)*math.factorial(q-2)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        return sum((n * (n - 1))*4 for n in collections.Counter(a*b for a, b in list(itertools.combinations(nums, 2))).values() if n >= 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=Counter([nums[i]*nums[j] for i in range(n) for j in range(i+1,n)])\n",
    "        print(cnt)\n",
    "        ans=0\n",
    "        for _,v in cnt.items():\n",
    "            ans+=v*(v-1)*4\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        dic = Counter([nums[i]*nums[j] for i in range(len(nums)) for j in range(i+1,len(nums))])\n",
    "        print(dic)\n",
    "        ans = 0\n",
    "        for key in dic:\n",
    "            ans += dic[key]*(dic[key]-1)*4\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        # 找到所有的2元组\n",
    "        ls = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                ls.append([nums[i], nums[j]])\n",
    "\n",
    "        # 根据二元组的乘积建立字典\n",
    "        d = collections.defaultdict(int)\n",
    "        for pair in ls:\n",
    "            d[pair[0] * pair[1]] += 1\n",
    "\n",
    "        # count\n",
    "        res = 0\n",
    "        for val in d.values():\n",
    "            if val > 1:\n",
    "                res += math.factorial(val)//(2 * math.factorial(val-2))\n",
    "        return res * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combination(self, k, n):\n",
    "        a = 1\n",
    "        b = 1\n",
    "        for i in range(1, k + 1):\n",
    "            b *= i\n",
    "        for i in range(0, k):\n",
    "            a *= (n - i)\n",
    "        return a // b\n",
    "\n",
    "    def tupleSameProduct(self, nums):\n",
    "        product_list = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                product = nums[i] * nums[j]\n",
    "                if product in product_list:\n",
    "                    product_list[product].append(i)\n",
    "                    product_list[product].append(j)\n",
    "                else:\n",
    "                    product_list[product] = [i, j]\n",
    "\n",
    "        ans = 0\n",
    "        for p in product_list.values():\n",
    "            if len(p) > 2:\n",
    "                tp = len(p) // 2\n",
    "                ans += 8 * self.combination(2, tp)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        nums_len = len(nums)\n",
    "        nums.sort()\n",
    "        list_data = []\n",
    "\n",
    "        for a in range(nums_len-1):\n",
    "            for c in range(a+1,nums_len):\n",
    "                list_data.append(nums[a]*nums[c])\n",
    "        print(Counter(list_data))\n",
    "        return sum(c * (c - 1) for c in Counter(list_data).values()) << 2\n",
    "\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "\n",
    "        two_nums = list(combinations(nums, 2))\n",
    "        cnt = Counter()\n",
    "\n",
    "        for two_num in two_nums:\n",
    "            cnt[two_num[0]*two_num[1]] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        cnt = dict(cnt)\n",
    "        for key in cnt.keys():\n",
    "            if cnt[key] > 1:\n",
    "                ans += cnt[key]*(cnt[key]-1) // 2\n",
    "        \n",
    "        return ans*8\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        nums_permutations = combinations(nums, 2)\n",
    "        nums_permutations_list = list(nums_permutations)\n",
    "\n",
    "        result = []\n",
    "\n",
    "        for i in nums_permutations_list:\n",
    "            result.append(i[0] * i[1])\n",
    "\n",
    "        counter_result = Counter(result)\n",
    "\n",
    "        result2 = []\n",
    "\n",
    "        for k,v in counter_result.items():\n",
    "            if v >= 2:\n",
    "                result2.append(v)\n",
    "\n",
    "        sum_tatol = 0\n",
    "        for val in result2:\n",
    "            sum_tatol = sum_tatol + 8 * sum(range(val))\n",
    "\n",
    "        return sum_tatol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, numbers: List[int]) -> int:\n",
    "        products, equal_pairs  = {}, {}\n",
    "        res = 0\n",
    "        for i in range(len(numbers)-1):\n",
    "            for j in range(i+1, len(numbers)):\n",
    "                product = numbers[i] * numbers[j]\n",
    "                if product in products:\n",
    "                    equal_pairs.setdefault(product, []).append((numbers[i], numbers[j]))\n",
    "                    if products[product] not in equal_pairs[product]:\n",
    "                        equal_pairs.setdefault(product, []).append(products[product])\n",
    "                else:\n",
    "                    products[product] = (numbers[i], numbers[j])\n",
    "        for k in equal_pairs:\n",
    "            res += math.comb(len(equal_pairs[k]), 2)\n",
    "\n",
    "        return res*8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        # 找到就+8\n",
    "        # 只要有一个数不相同就加8，算一种\n",
    "        n = len(nums)\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        from collections import defaultdict, Counter\n",
    "        find = defaultdict(list)\n",
    "        res, ans = [], []\n",
    "        for i in range(n):\n",
    "            tmp = [nums[i] * nums[j] for j in range(n) if j != i]\n",
    "            res.extend(tmp)\n",
    "            find[nums[i]].extend(tmp)\n",
    "        counter = Counter(res)\n",
    "        for i in counter.keys():\n",
    "            if counter[i] >= 4:\n",
    "                ans.append([i, counter[i]])\n",
    "        s = 0\n",
    "        for m, n in ans:\n",
    "            if n == 4:\n",
    "                s += 8\n",
    "            else:\n",
    "                s += ((n // 2) * (n // 2 - 1) // 2) * 8\n",
    "        # print(find)\n",
    "        print(ans)\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        total=0\n",
    "        length=len(nums)\n",
    "        tryList=[(j,i) for i in range(length) for j in range(i)]\n",
    "        sameList=[]\n",
    "        for i,j in tryList:\n",
    "            sameList.append(nums[i]*nums[j])\n",
    "        Counter=collections.Counter(sameList)\n",
    "        for i in Counter.values():\n",
    "            total+=(i*(i-1))/2\n",
    "        return int(total)*8\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        # 记录所有的乘积\n",
    "        product_list = []\n",
    "        length = len(nums)\n",
    "        # 记录乘积相等的组合数量\n",
    "        sum = 0\n",
    "        if length < 4:\n",
    "            return 0\n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length):\n",
    "                temp_product = nums[i] * nums[j]\n",
    "                product_list.append(temp_product)\n",
    "        product_dict = sorted(dict(Counter(product_list)).items(), key=lambda kv:(kv[1], kv[0]), reverse=True)\n",
    "\n",
    "        # 计算组合数量\n",
    "        def combination(n, k):\n",
    "            min_num = min(k, n - k)\n",
    "            result = 1\n",
    "            for temp_num in range(0, min_num):\n",
    "                result = result * (n - temp_num) / (min_num - temp_num)\n",
    "            return int(result)\n",
    "        for key, value in product_dict:\n",
    "            if value <= 1:\n",
    "                break\n",
    "            else:\n",
    "                sum += 8 * combination(value, 2)\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for i, n1 in enumerate(nums[:-1]):\n",
    "            for n2 in nums[::-1][:-i-1]:\n",
    "                # print(n1, n2)\n",
    "                tmp[n1 * n2].append((n1, n2))\n",
    "        for _, v in tmp.items():\n",
    "            if (j := len(v)) != 1:\n",
    "                res += (j - 1) * j // 2 * 8\n",
    "        # print(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tupleSameProduct(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        length = len(nums)\n",
    "\n",
    "        sum_dict = defaultdict(list)\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length):\n",
    "                sum_dict[nums[i] * nums[j]].append((nums[i], nums[j]))\n",
    "        result = 0    \n",
    "        for value in [value for value in sum_dict.values() if len(value) > 1]:\n",
    "            value_len = len(value)\n",
    "            result += value_len * (value_len - 1) * 8 // 2\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
